package com.lw.leetcode.arr.c;

import java.util.TreeSet;

/**
 * Created with IntelliJ IDEA.
 * 363. 矩形区域不超过 K 的最大数值和
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/13 17:36
 */
public class MaxSumSubmatrix {

    public static void main(String[] args) {
        MaxSumSubmatrix test = new MaxSumSubmatrix();

        // 2
        int[][] nums = {{1,0,1}, {0,-2,3}};
        int k = 2;

        // 2
//        int[][] nums = {{2, 2, -1}};
//        int k = 2;

        // -1
//        int[][] nums = {{2, 2, -1}};
//        int k = 0;

        // 8
//        int[][] nums = {
//                {5, -4, -3, 4},
//                {-3, -4, 4, 5},
//                {5, 1, 5, -4}};
//        int k = 8;

        int i = test.maxSumSubmatrix(nums, k);
        System.out.println(i);
    }

    private TreeSet<Integer> set = new TreeSet<>();
    private int v = Integer.MIN_VALUE;

    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] values = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                values[j] = matrix[j][i];
            }
            find(values, k);
            for (int j = i + 1; j < n; j++) {
                for (int t = 0; t < m; t++) {
                    values[t] += matrix[t][j];
                }
                find(values, k);
            }
        }
        return v;
    }

    private void find(int[] values, int k) {
        set.clear();
        set.add(0);
        int item = 0;
        for (int value : values) {
            item += value;
            Integer c = set.ceiling(item - k);
            set.add(item);
            if (c != null && item - c <= k && item - c > v) {
                v = item - c;
            }
        }
    }

}
